home *** CD-ROM | disk | FTP | other *** search
/ Stone Design / Stone Design.iso / Stone_Friends / Wave / WavesWorld / Source / IBPalettes / WW3DKit / list.c < prev    next >
Encoding:
C/C++ Source or Header  |  1995-03-22  |  10.1 KB  |  539 lines
  1.  
  2. #include <stdio.h>
  3. #include <stdlib.h>
  4. #include "list.h"
  5.  
  6.  
  7. int  list_resize();
  8.  
  9. /* list.c    a set of standard list routines.
  10.  
  11.     These routines implement a list of pointers to generic objects.
  12.  
  13.     the LIST pointer is a pointer to a header block for the list, which
  14.     points to an array of pointers to the generic data type.
  15.  
  16.  
  17. */
  18.  
  19. /* list_open:
  20.     create a list pointer for subsequent operations
  21. */
  22. LIST *
  23. list_open(size)
  24.     int    size;
  25. {
  26.     LIST    *l;
  27.  
  28.     if ( (l = ((LIST *) malloc ((unsigned) (sizeof (LIST))))) == NULL )
  29.     {    fprintf (stderr, "list_open: no room for list\n");
  30.         return NULL;
  31.     }
  32.     if (size <= 0)
  33.     {    fprintf (stderr, "list_open: bad size parameter\n");
  34.         return NULL;
  35.     }
  36.     l->listdiscipline = FIFO; /* queue by default */
  37.     if ( (l->list = (list_data_type **)malloc((unsigned) ((1+size) * (sizeof (list_data_type *))))) == NULL )
  38.     {    fprintf (stderr, "list_open: %d is too big for a list\n", size);
  39.         return NULL;
  40.     }
  41.     l->listlast = &l->list[size];
  42.     l->listhead = &l->list[0];
  43.     l->listtail = &l->list[0];
  44.     return (l);
  45. }
  46.  
  47.  
  48. /* list_close:
  49.     remove a list and free memory
  50. */
  51. void
  52. list_close(ld)
  53.     LIST    *ld;
  54. {
  55. /*^ if checks added   -paul */
  56.     if (ld != NULL)
  57.     {       if (ld->list != NULL)
  58.         {       free (ld->list);
  59.         }
  60.         free (ld);
  61.     }
  62. }
  63.  
  64. /* list_empty:
  65.     returns true if the list is empty,
  66.     false if the list is not empty.
  67. */
  68. int
  69. list_empty (ld)
  70.     LIST    *ld;
  71. {
  72.     if (ld == NULL)
  73.     {    fprintf (stderr, "list_empty: null list pointer\n");
  74.         return (-1);
  75.     } else
  76.     {    return (ld->listhead == ld->listtail);
  77.     }
  78. }
  79.  
  80. /* list_clear:
  81.     resets the list to so that list_empty returns true, and the list
  82.     can be filled to its max size.
  83. */
  84. void
  85. list_clear (ld)
  86.     LIST    *ld;
  87. {    
  88.     ld->listhead = ld->listtail;
  89. }
  90.  
  91. /* list_next:
  92.     returns pointer to the next element in the list
  93. */
  94. list_data_type **
  95. list_next(ld, p)
  96.     LIST        *ld;
  97.     list_data_type    **p;
  98. {
  99.     if (p == ld->listlast)
  100.     {    return (&ld->list[0]);
  101.     } else
  102.     {    return (p + 1);
  103.     } 
  104. }
  105.  
  106.  
  107. /* list_prev:
  108.     returns pointer to previous element in the list
  109. */
  110. list_data_type **
  111. list_prev(ld, n)
  112.     LIST    *ld;
  113.     list_data_type    **n;
  114. {
  115.     if (n == &ld->list[0])
  116.     {    return (ld->listlast);
  117.     } else
  118.     {    return (n - 1);
  119.     }
  120. }
  121.  
  122.  
  123. /* list_full:
  124.     returns ture if the list is full
  125. */
  126. int
  127. list_full(ld)
  128.     LIST    *ld;
  129. {    
  130.     return (list_prev(ld, ld->listhead) == ld->listtail);
  131. }
  132.  
  133.  
  134. /* list_push:
  135.     push an element onto the head of the list
  136.     returns pointer to position in list
  137. */
  138. list_data_type **
  139. list_push(ld, p)
  140.     LIST    *ld;
  141.     list_data_type    *p;
  142. {
  143.     if ( !list_full(ld))
  144.     {    *(ld->listhead) = p;
  145.         ld->listhead = list_prev(ld, ld->listhead);
  146.         return (list_next(ld, ld->listhead));
  147.     } else
  148.     {    return (NULL);
  149.     }
  150. }
  151.  
  152.  
  153. /* list_pop:
  154.     pops the top element off the head of the list
  155.     returns popped element or NULL if list is empty
  156. */
  157. list_data_type *
  158. list_pop(ld)
  159.     LIST    *ld;
  160. {
  161.     if (!list_empty(ld))
  162.     {    ld->listhead = list_next(ld, ld->listhead);
  163.         return (*(ld->listhead));
  164.     } else
  165.     {    return (NULL);
  166.     }
  167. }
  168.  
  169. /* list_top:
  170.     returns pointer to first element in list
  171.     NULL if list is empty
  172. */
  173. list_data_type *
  174. list_top(ld)
  175.     LIST    *ld;
  176. {
  177.     if (!list_empty(ld))
  178.     {    return (*list_next(ld, ld->listhead));
  179.     } else
  180.     {    return (NULL);
  181.     }
  182. }
  183.  
  184. /* list_enqueue:
  185.     puts the element passed at the back of the list
  186.     returns pointer to the new poition in the list,
  187.     or NULL if the list is full
  188. */
  189. list_data_type **
  190. list_enqueue(ld, p)
  191.     LIST    *ld;
  192.     list_data_type    *p;
  193. {
  194.     if (!list_full(ld))
  195.     {    ld->listtail = list_next (ld, ld->listtail);
  196.         *(ld->listtail) = p;
  197.         return (ld->listtail);
  198.     } else
  199.     {    return (NULL);
  200.     }
  201. }
  202.  
  203. /* list_unqueue:
  204.     removes the element at the end of the list (as if it
  205.     had just been added by list_enqueue).  returns a 
  206.     pointer to the element removed, or NULL if list
  207.     was empty
  208. */
  209. list_data_type *
  210. list_unqueue(ld)
  211.     LIST    *ld;
  212. {
  213.     if (!list_empty(ld))
  214.     {    ld->listtail = list_prev (ld, ld->listtail);
  215.         return (*list_next(ld, ld->listtail));
  216.     } else
  217.     {    return (NULL);
  218.     }
  219. }
  220.  
  221. /* list_dequeue:
  222.     removes the element from the front of the list
  223.     and returns it or NULL if the list was empty
  224. */
  225. list_data_type *
  226. list_dequeue(ld)
  227.     LIST    *ld;
  228. {
  229.     if (!list_empty(ld))
  230.     {    ld->listhead = list_next (ld, ld->listhead);
  231.         return (*(ld->listhead));
  232.     } else
  233.     {    return (NULL);
  234.     }
  235. }
  236.  
  237.  
  238. /* list_discipline:
  239.     sets the list discipline to stack or queue
  240.     returns the old type
  241. */
  242. int
  243. list_discipline(ld, discipline)
  244.     LIST    *ld;
  245.     int    discipline;
  246. {
  247.     int    odiscipline;
  248.  
  249.     odiscipline = ld->listdiscipline;
  250.     ld->listdiscipline = discipline;
  251.     return (odiscipline);
  252. }
  253.  
  254.  
  255. /* list_put:
  256.     adds an element to the list dependent on the list type
  257.     returns a pointer to the new list element
  258. */
  259. list_data_type **
  260. list_put(ld, p)
  261.     LIST    *ld;
  262.     list_data_type    *p;
  263. {
  264.     if (list_full (ld))
  265.     {    if (list_resize (ld, 2*list_size(ld)) < 0)
  266.         {    fprintf (stderr, "list_put: aborted\n");
  267.             return (NULL);
  268.         }
  269.     }
  270.     if (ld->listdiscipline == FIFO)
  271.     {    return (list_enqueue(ld, p));
  272.     } else
  273.     {    return (list_push(ld, p));
  274.     }
  275. }
  276.  
  277. /* list_get:
  278.     gets the next element from the list 
  279.     dependent on the queue type returns next element
  280. */
  281. list_data_type *
  282. list_get(ld)
  283.     LIST    *ld;
  284. {
  285.     if (list_empty (ld))
  286.     {    return (NULL);
  287.     }
  288.     if (ld->listdiscipline == FIFO)
  289.     {    return (list_dequeue(ld));
  290.     } else
  291.     {    return (list_pop(ld));
  292.     }
  293. }
  294.  
  295.  
  296. /* list_put_nth:
  297.     replaces the nth element of the list with the passed element
  298. */
  299. list_data_type    **
  300. list_put_nth (ld, n, element)
  301.     LIST    *ld;
  302.     int    n;
  303.     list_data_type    *element;
  304. {
  305.     list_data_type    **spot;
  306.     int        off;
  307.  
  308.     if (n >= list_size(ld))
  309.     {    return (NULL);
  310.     }
  311.     spot = 1 + ld->listhead + n;
  312.     off = spot - ld->listlast;
  313.     if (off <= 0)
  314.     {    *spot = element;
  315.         return (spot);
  316.     } else
  317.     {    *(ld->list + off) = element;
  318.         return (ld->list + off);
  319.     }
  320. }
  321.  
  322.  
  323. /* list_copy:
  324.     makes a copy of the from list and puts it into the to list
  325. */
  326. int
  327. list_copy(ldto, ldfrom)
  328.     LIST    *ldto, *ldfrom;
  329. {    
  330.     int    size, count;
  331.     list_data_type    *fromfinger;
  332.  
  333.     size = list_size (ldfrom);
  334.     if (size > ldto->listlast - ldto->list)
  335.     {    fprintf (stderr, "list_copy:  source list too big for destination\n");
  336.         return (-1);
  337.     }
  338.     list_clear (ldto);
  339.     for (count = 0; count < size; count++)
  340.     {    fromfinger = list_get_nth (ldfrom, count);
  341.         list_put (ldto, fromfinger);
  342.     }    
  343.     return (1);
  344. }
  345.  
  346. /* list_resize:
  347.     changes the size of the list, e.g. makes it larger so that 
  348.     a list which was full (true from list_full) will now not
  349.     be full
  350. */
  351. int
  352. list_resize (ld, size)
  353.     LIST    *ld;
  354.     int    size; /* new size of list array */
  355. {
  356.     LIST    *newlist, *temp;
  357.  
  358.     if (list_size(ld) >= size)
  359.     {    fprintf (stderr, "list_resize: new size too small\n");
  360.         return (int)NULL;
  361.     }
  362.     /* make new list as copy of old, only larger */
  363.     newlist = list_open (size);
  364.     if (list_copy (newlist, ld) < 0)
  365.     {    list_close (newlist);
  366.         fprintf (stderr, "list_resize: aborted\n");
  367.         return (-1);
  368.     }
  369.     newlist->listdiscipline = ld->listdiscipline; 
  370.  
  371.     /* move new list into old location */
  372.     temp = (LIST *) malloc ((unsigned) (sizeof (LIST)));
  373.     *temp = *ld; /* save old LIST header */
  374.     *ld = *newlist; /* make the passed pointer point to the new header */
  375.     list_close (temp); /* get rid of the original list */
  376.     free (newlist); /* get rid of extra header */
  377.     return (1);
  378. }
  379.  
  380. /* list_delete_nth:
  381.     removes the nth element from the list and closes in the remaining
  382.     elements of the list
  383. */
  384. list_data_type    *
  385. list_delete_nth(ld, n)
  386.     LIST *ld;
  387.     int n;
  388. {
  389.     int size,count;
  390.     list_data_type *tmp, *return_el;
  391.  
  392.     size = list_size(ld);
  393.     if (n >= size) 
  394.     {    fprintf(stderr, "list_delete_nth:  n is greater than list size\n");
  395.         return(NULL);
  396.     }
  397.     return_el = list_get_nth (ld, n);
  398.     for (count = n; count < size-1; count++)
  399.     {    tmp = (list_data_type *) list_get_nth(ld, count+1);
  400.         list_put_nth(ld, count, tmp);
  401.     }
  402.     list_unqueue(ld);
  403.     return (return_el);
  404. }  /* list_delete_nth */
  405.  
  406.  
  407. /* list_delete_element:
  408.     removes the element from the list and closes in the remaining
  409.     elements of the list
  410. */
  411. list_data_type    *
  412. list_delete_element(ld, element)
  413.     LIST *ld;
  414.     list_data_type    *element;
  415. {
  416.     int size,count;
  417.     list_data_type *tmp;
  418.  
  419.     if (ld == NULL)
  420.     {    fprintf (stderr, "list_delete_element: bad list\n");
  421.         return (NULL);
  422.     } 
  423.     size = list_size(ld);
  424.     for (count = 0; count < size; count++)
  425.     {    tmp = (list_data_type *) list_get_nth(ld, count);
  426.         if (tmp == element)
  427.         {    list_delete_nth(ld, count);
  428.             return (element);
  429.         }
  430.     }
  431.     return (NULL);
  432. }  /* list_delete_element */
  433.  
  434.  
  435. /* list_insert_nth:
  436.     puts the passed element into the nth location in the passed list,
  437.     and moves the old elements back to make room.  the list becomes
  438.     one larger.  returns the pointer to the new location, or NULL if
  439.     there was an error.  list_insert_nth will double the size of the 
  440.     list if there was no room for the inserted element.
  441. */
  442. list_data_type **
  443. list_insert_nth (ld, n, p)
  444.     LIST    *ld;
  445.     int    n;
  446.     list_data_type    *p;
  447. {
  448.     int    size, count;
  449.     list_data_type    *t;
  450.  
  451.     if (n < 0 || n >= list_size(ld))
  452.     {    fprintf (stderr, "list_insert_nth: bad instert location %d\n",n);
  453.         return (NULL);
  454.     }
  455.     if (list_full (ld))
  456.     {    if (list_resize (ld, 2*list_size(ld)) < 0)
  457.         {    fprintf (stderr, "list_insert_nth: aborted\n");
  458.             return (NULL);
  459.         }
  460.     }
  461.     list_enqueue (ld, p);  /* add a new spot at the end of the list */
  462.     size = list_size (ld);
  463.         /* slide all behind nth back */
  464.     for (count = size - 1; count >=n; count--)
  465.     {    t = list_get_nth (ld, count-1);
  466.         list_put_nth (ld, count, t);
  467.     }
  468.     return (list_put_nth (ld, n, p));  /* p becomes nth */
  469. }
  470.  
  471.  
  472. int
  473. list_element_get_index (ld, el)
  474.     LIST    *ld;
  475.     list_data_type    *el;
  476. {
  477.     int    size, count;
  478.  
  479.     size = list_size (ld);
  480.     for (count = 0; count < size; count++)
  481.     {    if (el == list_get_nth (ld, count))
  482.         {    return (count);
  483.         }
  484.     }
  485.     return (-1);
  486. }
  487.  
  488. /* nb: list_size and list_get_nth have been replaced by macro
  489. versions in list.h.  These are kept around for any files that have
  490. not been recompiled with the new list.h */
  491.  
  492. #undef list_size
  493. /* list_size:
  494.     returns the number of elements in the list
  495. */
  496. int
  497. list_size (ld)
  498.     LIST    *ld;
  499. {
  500.     int     size;
  501.  
  502.     if (ld == NULL)
  503.     {    return (0);
  504.     }
  505.     if (ld->listhead > ld->listtail)
  506.     {    size = ld->listlast - ld->listhead;
  507.         size += ld->listtail - ld->list + 1;
  508.         return (size);
  509.     } else
  510.     {    size = ld->listtail - ld->listhead;
  511.         return (size);
  512.     }
  513. }
  514.  
  515. #undef list_get_nth
  516. /* list_get_nth:
  517.     returns the nth element in the list (doesn't delete it)
  518. */
  519. list_data_type    *
  520. list_get_nth (ld, n)
  521.     LIST    *ld;
  522.     int    n;
  523. {
  524.     list_data_type    **spot;
  525.     int        off;
  526.  
  527.     if (n >= list_size(ld))
  528.     {    return (NULL);
  529.     }
  530.     spot = 1 + ld->listhead + n;
  531.     off = spot - ld->listlast;
  532.     if (off <= 0)
  533.     {    return (*spot);
  534.     } else
  535.     {    return (*(ld->list + off - 1));
  536.     }
  537. }
  538.  
  539.